/**
 * @file list.h Schnittstelle einer Bibliothek fuer Listenoperationen.
 *
 * Listenelemente sind ganzzahlige Werte groesser gleich Null.
 * Listen koennen jeden Wert nur einmal enthalten.
 * Listen sind aufsteigend sortiert.
 * Listen sind als rekursive Struktur implementiert (einfach verkette Listen).
 *
 * @author Arthur, Markus
 */

#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include "list.h"

/*interne Funktionen*/

/*Implementierung der Schnittstellenfunktionen*/


extern List list_mkEmpty (void){
return (List)0;
}

extern int list_isEmpty (List l){
return l==(List)0;
}

extern Element list_head (List l){
assert(!list_isEmpty(l));
return l->value;
}

extern List list_tail (List l){
assert(!list_isEmpty(l));
return l->next;
}

extern List list_removeHead (List l){
List res=list_tail(l);
assert(!list_isEmpty(l));
free(l);
return res;
}

extern List list_cons (Element e, List l){
List res;
res=malloc(sizeof(Element)+sizeof(List));
res->value=e;
res->next=l;
return res;
}

extern unsigned long list_length (List l){
if (list_isEmpty(l)) return 0;
else return (1 + list_length(list_tail(l)));
}

extern Element list_at (List l, unsigned long i){
if (list_isEmpty(l)) return (Element)0;
if (i==0) return list_head(l);
else return list_at(list_tail(l),i-1);
}

extern int list_isIn (Element e, List l){
if (list_isEmpty(l)) return 0;
if (list_head(l)==e) return 1;
else return list_isIn(e,list_tail(l));
}

extern List list_insertElem (Element e, List l){
if (list_isEmpty(l) || e<list_head(l))
return list_cons(e,l);
if (e==list_head(l)) return l; /* Element ist schon in Liste vorhanden */
l->next=list_insertElem(e,list_tail(l));
return l;
}

extern List list_removeElem (Element e, List l){
if (list_isEmpty(l)) return l;

if (list_eqElement(list_head(l),e))
  return list_removeHead(l);
else{
  l->next=list_removeElem(e,list_tail(l));
  return l;
  }
}

extern List list_removeAllElems (List l){
if (list_isEmpty(l)) return l;
  return list_removeAllElems (list_removeElem(list_head(l), l));
}

